;; ta-solver-starter.rkt



;  PROBLEM 1:
;  
;  Consider a social network similar to Twitter called Chirper. Each user has a name, a note about
;  whether or not they are a verified user, and follows some number of people. 
;  
;  Design a data definition for Chirper, including a template that is tail recursive and avoids 
;  cycles. 
;  
;  Then design a function called most-followers which determines which user in a Chirper Network is 
;  followed by the most people.
;  



(define-struct chirper (name verified? following) )
;;(make-chirper (String Boolean ListOfChirpers ))
;; interp. name: String representing the user's name
;;         verfied?: Boolean telling whether the chirper is verfied or not
;;         following: ListOfChirpers, stating the chirpers that are followed

(define person1 (make-chirper "Young Gravy" true empty ))
(define person2 (make-chirper "TM Sauce" true empty ))

(define person7 (make-chirper "Tego" true (list person1 person2 ) ))
(define person8 (make-chirper "Uq" false (list person6)  ))

(define person3 (make-chirper "Joe" false (list person4) ))
(define person4 (make-chirper "Jane" false (list person3) ))

(define person5 (make-chirper "Halo" false (list person4 person1 person2 ) ))
(define person6 (make-chirper "FR" false (list person7 ) ))





;  PROBLEM 2:
;  
;  In UBC's version of How to Code, there are often more than 800 students taking 
;  the course in any given semester, meaning there are often over 40 Teaching Assistants. 
;  
;  Designing a schedule for them by hand is hard work - luckily we've learned enough now to write 
;  a program to do it for us! 
;  
;  Below are some data definitions for a simplified version of a TA schedule. There are some 
;  number of slots that must be filled, each represented by a natural number. Each TA is 
;  available for some of these slots, and has a maximum number of shifts they can work. 
;  
;  Design a search program that consumes a list of TAs and a list of Slots, and produces one
;  valid schedule where each Slot is assigned to a TA, and no TA is working more than their 
;  maximum shifts. If no such schedules exist, produce false. 
; 
;  You should supplement the given check-expects and remember to follow the recipe!



;; Slot is Natural
;; interp. each TA slot has a number, is the same length, and none overlap

(define-struct ta (name max avail))
;; TA is (make-ta String Natural (listof Slot))
;; interp. the TA's name, number of slots they can work, and slots they're available for

(define SOBA (make-ta "Soba" 2 (list 1 3)))
(define UDON (make-ta "Udon" 1 (list 3 4)))
(define RAMEN (make-ta "Ramen" 1 (list 2)))

(define NOODLE-TAs (list SOBA UDON RAMEN))



(define-struct assignment (ta slot))
;; Assignment is (make-assignment TA Slot)
;; interp. the TA is assigned to work the slot

;; Schedule is (listof Assignment)


;; ============================= FUNCTIONS


;; (listof TA) (listof Slot) -> Schedule or false
;; produce valid schedule given TAs and Slots; false if impossible

(check-expect (schedule-tas empty empty) empty)
(check-expect (schedule-tas empty (list 1 2)) false)
(check-expect (schedule-tas (list SOBA) empty) empty)

(check-expect (schedule-tas (list SOBA) (list 1)) (list (make-assignment SOBA 1)))
(check-expect (schedule-tas (list SOBA) (list 2)) false)
(check-expect (schedule-tas (list SOBA) (list 1 3)) (list (make-assignment SOBA 3)
                                                          (make-assignment SOBA 1)))
#;
(check-expect (schedule-tas NOODLE-TAs (list 1 2 3 4)) 
              (list
               (make-assignment UDON 4)
               (make-assignment SOBA 3)
               (make-assignment RAMEN 2)
               (make-assignment SOBA 1)))

(check-expect (schedule-tas NOODLE-TAs (list 1 2 3 4 5)) false)


(define (schedule-tas tas slots) (local
                                   [(define (schedule-tas0 tas slots assignments)
                                      (cond[(and (empty? tas)(not (empty? slots))) false]
                                           [(empty? slots) assignments]
                                           
                                           [else
                                            (local [(define rslt (solve-ta (first tas) slots ) )
                                                    
                                                    (define evaluate-ta-schedule 
                                                      (if (equal? false rslt)
                                                          (schedule-tas0 (rest tas) slots assignments );Ta doesnt fit in schedule
                                                          (schedule-tas0 (rest tas) (rm  rslt slots ) (append rslt assignments)  )
                                                          )  )]
                                              
                                               evaluate-ta-schedule )
                                            ]  )) ]
                                   (schedule-tas0 tas slots empty) ) )



(define STIR-FRY (make-ta "STIR FRY" 0 empty))
(check-expect (solve-ta SOBA (list 1 2 3 4 5 ) ) (list (make-assignment SOBA 3)
                                                       (make-assignment SOBA 1)) )

(check-expect (solve-ta UDON (list 1 2 5) ) false )
(check-expect (solve-ta STIR-FRY (list 1 2 3 4 5 ) ) false)

(check-expect (solve-ta RAMEN (list 1 2 3 4 5 ) ) (list (make-assignment RAMEN 2) ) )



;; ta , slot -> False or ListOf Assignments
;; interp. finds all available slot for the given ta and  produces a ListOf assignment(s), False otherwise
;; assumes slots is not empty

;; Remeber slots list do not need to be modified in this function
(define (solve-ta ta slots)
                     (local [(define (solve-ta0 los num_shifts slots acct )
                               (cond [(and (empty? acct) (zero? num_shifts)) false ]
                                     [(zero? num_shifts) acct ]
                                     [(and (empty? acct) (empty? los)) false ]
                                     [(empty? los) acct ]
                                     [else
                                      (if (member? (first los) slots )
                                          (solve-ta0 (rest los) (sub1 num_shifts) slots (cons (make-assignment ta (first los) ) acct ) )
                                          (solve-ta0 (rest los) num_shifts slots acct )
                                          ) ]) )]
                       (solve-ta0 (ta-avail ta) (ta-max ta) slots empty ) ))

(check-expect (rm  empty (list 1 2 3 4 5 ) ) (list 1 2 3 4 5) ) ;;No assignments
(check-expect (rm  (list 1 2 3 4 5 ) empty  ) empty )           ;;No slots

;;More assignments than slots
(check-expect (rm  (list (make-assignment SOBA 1)
                         (make-assignment SOBA 2)
                         (make-assignment SOBA 3)
                         (make-assignment SOBA 4)
                         (make-assignment SOBA 5)
                         (make-assignment SOBA 6)
                         (make-assignment SOBA 7)
                         (make-assignment SOBA 8) )
                   (list 1 2 3 4 5 ) )
              empty )
;;More slots than assignments
(check-expect (rm  (list (make-assignment SOBA 3)
                         (make-assignment SOBA 1) )
                   (list 1 2 3 4 5 ) )
              (list 2 4 5) )
;;More slots than assignments
(check-expect (rm  (list (make-assignment SOBA 1)
                         (make-assignment SOBA 3) )
                   (list 1 2 3 4 5 ) )
              (list 2 4 5) )

;;Same amount of slots as assignments
(check-expect (rm  (list (make-assignment SOBA 1)
                         (make-assignment SOBA 2)
                         (make-assignment SOBA 3)
                         (make-assignment SOBA 4)
                         (make-assignment SOBA 5))
                   (list 1 2 3 4 5 ) )
              empty )



;;Listof Assigments and ListOf Numbers -> ListOf Numbers
;; interp. produces a lon with all the slots that have been taken in the ListOf Assignments removed
 
(define (rm loa slots) 
                     (cond [(empty? loa) slots ]
                           [(empty? slots) empty] ;; More assignments than slots
                           [else
                             (rm (rest loa)  (remove-all (assignment-slot (first loa)) slots )  )
                                 ] ) )